
from typing import List
class Solution:
    # 双指针
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        left = 0
        for right in range(n):
            if nums[right] != val:
                nums[left] = nums[right]
                left+=1
        return  left
    '''
    复杂度分析
    时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多两次。
    空间复杂度：O(1)。我们只需要常数的空间保存若干变量。
    '''


    # 双指针优化
    def removeElement2(self, nums: List[int], val: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            if nums[left] == val:
                nums[left] = nums[right - 1]
                right -= 1
            else:
                left += 1
        return left
    '''
    复杂度分析
    时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多一次。
    空间复杂度：O(1)。我们只需要常数的空间保存若干变量。
    '''

print(Solution().removeElement([3,2,2,3],3))